void paixu() {
  List<int> numbers = [4, 2, 1, 3];

  // 希尔排序
  List<int> shellSortList = List.from(numbers);
  shellSort(shellSortList);
  print('Shell Sort: $shellSortList'); // 输出 [1, 2, 3, 4]

  // 选择排序
  List<int> selectionSortList = List.from(numbers);
  selectionSort(selectionSortList);
  print('Selection Sort: $selectionSortList'); // 输出 [1, 2, 3, 4]

  // 堆排序
  List<int> heapSortList = List.from(numbers);
  heapSort(heapSortList);
  print('Heap Sort: $heapSortList'); // 输出 [1, 2, 3, 4]

  // 冒泡排序
  List<int> bubbleSortList = List.from(numbers);
  bubbleSort(bubbleSortList);
  print('Bubble Sort: $bubbleSortList'); // 输出 [1, 2, 3, 4]

  // 快速排序
  List<int> quickSortList = List.from(numbers);
  quickSort(quickSortList, 0, quickSortList.length - 1);
  print('Quick Sort: $quickSortList'); // 输出 [1, 2, 3, 4]

  // 归并排序
  List<int> mergeSortList = List.from(numbers);
  mergeSort(mergeSortList, 0, mergeSortList.length - 1);
  print('Merge Sort: $mergeSortList'); // 输出 [1, 2, 3, 4]

  // 计数排序
  List<int> countingSortList = List.from(numbers);
  countingSort(countingSortList);
  print('Counting Sort: $countingSortList'); // 输出 [1, 2, 3, 4]
}

// 希尔排序
void shellSort(List<int> list) {
  int gap = list.length ~/ 2;
  while (gap > 0) {
    for (int i = gap; i < list.length; i++) {
      int temp = list[i];
      int j = i;
      while (j >= gap && list[j - gap] > temp) {
        list[j] = list[j - gap];
        j -= gap;
      }
      list[j] = temp;
    }
    gap ~/= 2;
  }
}

// 选择排序
void selectionSort(List<int> list) {
  for (int i = 0; i < list.length - 1; i++) {
    int minIndex = i;
    for (int j = i + 1; j < list.length; j++) {
      if (list[j] < list[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex != i) {
      swap(list, i, minIndex);
    }
  }
}

// 堆排序
void heapSort(List<int> list) {
  int n = list.length;

  for (int i = n ~/ 2 - 1; i >= 0; i--) {
    heapify(list, n, i);
  }

  for (int i = n - 1; i >= 0; i--) {
    swap(list, 0, i);
    heapify(list, i, 0);
  }
}

void heapify(List<int> list, int n, int i) {
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && list[left] > list[largest]) {
    largest = left;
  }

  if (right < n && list[right] > list[largest]) {
    largest = right;
  }

  if (largest != i) {
    swap(list, i, largest);
    heapify(list, n, largest);
  }
}

// 冒泡排序
void bubbleSort(List<int> list) {
  int n = list.length;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (list[j] > list[j + 1]) {
        swap(list, j, j + 1);
      }
    }
  }
}

// 快速排序
void quickSort(List<int> list, int low, int high) {
  if (low < high) {
    int pi = partition(list, low, high);

    quickSort(list, low, pi - 1);
    quickSort(list, pi + 1, high);
  }
}

int partition(List<int> list, int low, int high) {
  int pivot = list[high];
  int i = low - 1;

  for (int j = low; j < high; j++) {
    if (list[j] < pivot) {
      i++;
      swap(list, i, j);
    }
  }

  swap(list, i + 1, high);
  return i + 1;
}

// 归并排序
void mergeSort(List<int> list, int left, int right) {
  if (left < right) {
    int mid = (left + right) ~/ 2;

    mergeSort(list, left, mid);
    mergeSort(list, mid + 1, right);

    merge(list, left, mid, right);
  }
}

void merge(List<int> list, int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;

  List leftArray = [n1];
  List rightArray = [n2];

  for (int i = 0; i < n1; i++) {
    leftArray[i] = list[left + i];
  }
  for (int j = 0; j < n2; j++) {
    rightArray[j] = list[mid + 1 + j];
  }

  int i = 0, j = 0;
  int k = left;

  while (i < n1 && j < n2) {
    if (leftArray[i] <= rightArray[j]) {
      list[k] = leftArray[i];
      i++;
    } else {
      list[k] = rightArray[j];
      j++;
    }
    k++;
  }

  while (i < n1) {
    list[k] = leftArray[i];
    i++;
    k++;
  }

  while (j < n2) {
    list[k] = rightArray[j];
    j++;
    k++;
  }
}

// 计数排序
void countingSort(List<int> list) {
  int n = list.length;
  List<int> output = List.filled(n, 0);

  int maxNum = list[0];
  for (int i = 1; i < n; i++) {
    if (list[i] > maxNum) {
      maxNum = list[i];
    }
  }

  List<int> countArray = List.filled(maxNum + 1, 0);

  for (int i = 0; i < n; i++) {
    countArray[list[i]]++;
  }

  for (int i = 1; i <= maxNum; i++) {
    countArray[i] += countArray[i - 1];
  }

  for (int i = n - 1; i >= 0; i--) {
    output[countArray[list[i]] - 1] = list[i];
    countArray[list[i]]--;
  }

  for (int i = 0; i < n; i++) {
    list[i] = output[i];
  }
}

// 交换数组中两个元素的位置
void swap(List<int> list, int i, int j) {
  int temp = list[i];
  list[i] = list[j];
  list[j] = temp;
}
